package algorithms4g

import (
	"fmt"
)

/**
回文链表-复制数组，左右指针迭代
*/
func palindromeList(head *ListNode) bool {
	nums := []int{}
	for head != nil {
		nums = append(nums, head.Val)
		head = head.Next
	}
	left, right := 0, len(nums)-1
	for left < right {
		if nums[left] != nums[right] {
			return false
		}
		left++
		right--
	}
	return true
}

/**
回文链表-递归
*/
var frontPointer *ListNode

func palindromeList2(head *ListNode) bool {
	frontPointer = head
	return palindrome(head)
}

func palindrome(currentNode *ListNode) bool {
	if currentNode != nil {
		if !palindrome(currentNode.Next) {
			return false
		}
		if currentNode.Val != frontPointer.Val {
			return false
		}
		frontPointer = frontPointer.Next
	}
	return true
}

/**
回文链表-快慢指针
*/
func palindromeList3(head *ListNode) bool {
	//快慢指针找到中间节点
	fast, slow := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	//反转后半部分链表
	afterHead := slow.Next
	revAfterHead := reverseList(afterHead)
	//比较后半部份和链表前半部分
	result := true
	for result && revAfterHead != nil {
		if head.Val != revAfterHead.Val {
			result = false
		}
		head = head.Next
		revAfterHead = revAfterHead.Next
	}
	//恢复链表
	slow.Next = reverseList(revAfterHead)
	return result
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode = nil
	curr := head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}
func init() {
	l1 := &ListNode{4, nil}
	l2 := &ListNode{3, l1}
	l3 := &ListNode{6, l2}
	l4 := &ListNode{6, l3}
	l5 := &ListNode{3, l4}
	l6 := &ListNode{4, l5}
	res := palindromeList(l6)
	fmt.Println("回文链表-复制数组", res)

	res2 := palindromeList2(l6)
	fmt.Println("回文链表-递归", res2)
}
